Search for: All records

Motivated by mutation processes occurring in in vivo DNA-storage applications, a channel that mutates stored strings by duplicating substrings as well as substituting symbols is studied. Two models of such a channel are considered: one in which the substitutions occur only within the duplicated substrings, and one in which the location of substitutions is unrestricted. Both error-detecting and error-correcting codes are constructed, which can handle correctly any number of tandem duplications of a fixed length k, and at most a single substitution occurring at any time during the mutation process. 

Mutations play a significant role in evolution since they lead to genomic diversity. Among different types of mutations, duplication is thought to be one of the most important. Motivated by the theory of evolution by duplication, we consider a stochastic model for the evolution of sequences under noisy tandem duplication, where segments of the sequences are replicated and approximate copies are added to the sequence. Our goal is to study the statistical properties of the sequence after a given number of mutations. To do so, we study the k-mer frequencies of the evolving sequence. We first bound the expected frequencies of different k-mers after n mutations and relate the convergence rate of the expected trajectories to the parameters of the model (probabilities of different mutations). Then we extend our analysis to second moments of the k-mer trajectories, which allow us to better characterize their evolution. Finally, we will demonstrate the application of the proposed methods to bounding waiting times, the first such results for complex mutation systems.